"No Freedom" được viết và sản xuất bởi Dido và Rick Nowels, người trước đây tham gia hợp tác trong bản nhạc ăn khách, "White Flag" của cô, trong khi Rollo Armstrong tham gia đồng sản xuất nó.[2] Ca khúc được viết lúc Dido đang mang thai đứa con trai đầu lòng của cô, Stanley và được thu âm ngay trước khi cô sinh Stanley.[3] Cô thu ca khúc này ở Los Angeles, Hoa Kỳ tại phòng thu Rick Nowels và hoàn thành ca khúc tại nhà cùng với anh trai Rollo Armstrong của mình.[4]

Trước lúc phát hành đĩa đơn, một đoạn nhạc từ bản phối lại của DJ COBRA bị tuồn lên Internet. Giai điệu của bản đó hoàn toàn khác so với bản gốc. Sau đó, Dido giải thích trên tài khoản Twitter của mình, DJ COBRA đưa nhầm bản thu thử phối lại cũ thay vì bản gốc.[5]

Lời bài hát nói về một chuyện tình đau khổ.[3] Theo Dido, lời bài hát còn có ý nghĩa nhiều hơn là chỉ ở tình yêu.[4] Đoạn điệp khúc, "No freedom without love" nhận được nhiều phản hồi từ nhóm chống đối tại Syria. Dido có chia sẻ với BBC News sau khi phát hành đĩa đơn này, cô nhận được nhiều "lá thư từ những người đang ở giữa chiến tranh."[3] Ca khúc là một bản folk pop, cùng với tiếng đàn guitar acoustic, có hơi hướng reggae[6] và có tiết tấu trung hoà vào giọng mộng mị của Dido.[7]